Exploiting temporal information in Web search

Time plays important roles in Web search, because most Web pages contain temporal information and a lot of Web queries are time-related. How to integrate temporal information in Web search engines has been a research focus in recent years. However, traditional search engines have little support in processing temporal-textual Web queries. Aiming at solving this problem, in this paper, we concentrate on the extraction of the focused time for Web pages, which refers to the most appropriate time associated with Web pages, and then we used focused time to improve the search efficiency for time-sensitive queries. In particular, three critical issues are deeply studied in this paper. The first issue is to extract implicit temporal expressions from Web pages. The second one is to determine the focused time among all the extracted temporal information, and the last issue is to integrate focused time into a search engine. For the first issue, we propose a new dynamic approach to resolve the implicit temporal expressions in Web pages. For the second issue, we present a score model to determine the focused time for Web pages. Our score model takes into account both the frequency of temporal information in Web pages and the containment relationship among temporal information. For the third issue, we combine the textual similarity and the temporal similarity between queries and documents in the ranking process. To evaluate the effectiveness and efficiency of the proposed approaches, we build a prototype system called Time-Aware Search Engine (TASE). TASE is able to extract both the explicit and implicit temporal expressions for Web pages, and calculate the relevant score between Web pages and each temporal expression, and re-rank search results based on the temporal-textual relevance between Web pages and queries. Finally, we conduct experiments on real data sets. The results show that our approach has high accuracy in resolving implicit temporal expressions and extracting focused time, and has better ranking effectiveness for time-sensitive Web queries than its competitor algorithms.     

An architectural design for effective information retrieval in semantic web

The current web IR system retrieves relevant information only based on the keywords which is inadequate for that vast amount of data. It provides limited capabilities to capture the concepts of the user needs and the relation between the keywords. These limitations lead to the idea of the user conceptual search which includes concepts and meanings. This study deals with the Semantic Based Information Retrieval System for a semantic web search and presented with an improved algorithm to retrieve the information in a more efficient way.This architecture takes as input a list of plain keywords provided by the user and the query is converted into semantic query. This conversion is carried out with the help of the domain concepts of the pre-existing domain ontologies and a third party thesaurus and discover semantic relationship between them in runtime. The relevant information for the semantic query is retrieved and ranked according to the relevancy with the help of an improved algorithm. The performance analysis shows that the proposed system can improve the accuracy and effectiveness for retrieving relevant web documents compared to the existing systems.     

Reactive Search strategies using Reinforcement Learning,local search algorithms and Variable Neighborhood Search

Optimization techniques known as metaheuristics have been applied successfully to solve different problems, in which their development is characterized by the appropriate selection of parameters (values) for its execution. Where the adjustment of a parameter is required, this parameter will be tested until viable results are obtained. Normally, such adjustments are made by the developer deploying the metaheuristic. The quality of the results of a test instance [The term instance is used to refer to the assignment of values to the input variables of a problem.] will not be transferred to the instances that were not tested yet and its feedback may require a slow process of “trial and error” where the algorithm has to be adjusted for a specific application. Within this context of metaheuristics the Reactive Search emerged defending the integration of machine learning within heuristic searches for solving complex optimization problems. Based in the integration that the Reactive Search proposes between machine learning and metaheuristics, emerged the idea of putting Reinforcement Learning, more specifically the Q-learning algorithm with a reactive behavior, to select which local search is the most appropriate in a given time of a search, to succeed another local search that can not improve the current solution in the VNS metaheuristic. In this work we propose a reactive implementation using Reinforcement Learning for the self-tuning of the implemented algorithm, applied to the Symmetric Travelling Salesman Problem.     

基于MTPM和DPM的多无人机协同广域目标搜索滚动时域决策

传统的协同搜索决策方法在目标引导和机间协同方面存在不足. 研究建立了基于分布概率预测的目标概率图（Target probability map,TPM）初始化方法和基于贝叶斯准则的目标概率图动态更新方法,形成了修正目标概率图（Modified TPM,MTPM）及其运算机理.考虑对任务子区域进行可控回访,定义了数字信息素图（Digital pheromone map,DPM）,建立了数字信息素图使用方法及更新机理.设计了基于MTPM和DPM的寻优指标,建立了基于滚动时域控制的协同搜索决策方法（MTPM-DPM-RHC method,MDR）.仿真表明: 1） MTPM能有效降低对目标的虚警率和漏检率;2） DPM能有效实现对任务区域可控回访;3） MDR方法的遍历能力、重访能力和目标搜索效率均优于已有方法.     

用于提高谷歌图像搜索结果的二分类器在线学习方法

对于基于关键词的图像检索,利用检索结果的视觉相似性学习二分类器有望成为改善检索结果的最有效途径之一. 为改善搜索引擎的搜索结果,本文提出一种算法框架并且基于此框架着重研究训练数据选择这一关键问题. 训练数据选择过程由两个阶段组成:1）训练数据初始化以开始分类器学习过程;2）分类器迭代学习过程中的动态数据选择. 对于初始训练数据的选择,我们探讨了基于聚类和基于排序两种方法,并且对比了自动训练数据选择与人工标注的结果. 对于动态数据选择,我们比较了支持向量机和基于最大最小后验伪概率的贝叶斯分类器的分类效果. 组合上述两个阶段的不同方法,我们得到了8种不同的算法,并将其用于谷歌搜索引擎进行基于关键词的图像检索. 实验结果证明,如何从含有噪声的搜索结果中选择训练数据是搜索结果改善的关键问题. 实验显示我们的方法能够有效的改善谷歌搜索的结果,尤其是排序在前的结果. 尽早为用户提供更相关的结果能够更大程度的减少用户逐个翻页查看结果的工作. 另外,如何使自动训练数据选择与人工标注媲美仍是需要继续研究的一个问题.     

Interactive fuzzy stochastic multi-level 0–1 programming using tabu search and probability maximization

In this paper, we consider interactive fuzzy programming for multi-level 0–1 programming problems involving random variable coefficients both in objective functions and constraints. Following the probability maximization model together with the concept of chance constraints, the formulated stochastic multi-level 0–1 programming problems are transformed into deterministic ones. Taking into account vagueness of judgments of the decision makers, we present interactive fuzzy programming. In the proposed interactive method, after determining the fuzzy goals of the decision makers at all levels, a satisfactory solution is derived efficiently by updating satisfactory levels of the decision makers with considerations of overall satisfactory balance among all levels. For solving the transformed deterministic problems efficiently, we also introduce novel tabu search for general 0–1 programming problems. A numerical example for a three-level 0–1 programming problem is provided to illustrate the proposed method.     

Context matters: The structure of task goals affects accuracy in multiple-target visual search

Career visual searchers such as radiologists and airport security screeners strive to conduct accurate visual searches, but despite extensive training, errors still occur. A key difference between searches in radiology and airport security is the structure of the search task: Radiologists typically scan a certain number of medical images (fixed objective), and airport security screeners typically search X-rays for a specified time period (fixed duration). Might these structural differences affect accuracy? We compared performance on a search task administered either under constraints that approximated radiology or airport security. Some displays contained more than one target because the presence of multiple targets is an established source of errors for career searchers, and accuracy for additional targets tends to be especially sensitive to contextual conditions. Results indicate that participants searching within the fixed objective framework produced more multiple-target search errors; thus, adopting a fixed duration framework could improve accuracy for career searchers.     

Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time

This paper deals with the problem of scheduling a flow shop operating in a sequence dependent setup time environment. The objective is to determine the sequence that minimises the makespan. Two efficient neighbourhood search-based heuristics have been developed and tested using 960 problems, and the results obtained reveal their usefulness. The algorithms make use of two existing constructive heuristics. A neighbourhood search known as variable neighbourhood descent is used to improve the two constructive heuristics. Experimentation is carried out on the 96 groups of problems with 10 problem instances in each group. Performance analysis is carried out using the relative performance improvement of each heuristic. The analysis shows a consistently better performance of the neighbourhood-based improvement heuristics. A paired comparison test is used for validating the superiority of the proposed heuristics. The statistical analysis reveals that the performance of the neighbourhood-based heuristics is very much dependent on the initial constructive heuristics used.     

Tabu-based GIS for solving the vehicle routing problem

Besides being a hard combinatorial problem, the VRP is also a spatial problem. Hence, effective decision making in this field strongly requires the integration of GIS and optimization systems (GIS-O). This article integrates GIS and optimization tools for solving the vehicle routing problem with loading and distance requirements (DCVRP). A general outline of the multi-step integration is pointed out showing the interaction of the GIS and the spatial optimization according to the loose coupling strategy. The computational performance of the TS-VRP algorithm for the DCVRP turned out to be quite efficient on both computation time and solution quality. The Tunisian case study well illustrates the incentive behind using such a spatial decision support system that allows the management of the problem from the data acquisition to the visualization of possible simulation scenarios in a more realistic way.     

An improved global-best harmony search algorithm for faster optimization

In this paper, an improved global-best harmony search algorithm, named IGHS, is proposed. In the IGHS algorithm, initialization based on opposition-based learning for improving the solution quality of the initial harmony memory, a new improvisation scheme based on differential evolution for enhancing the local search ability, a modified random consideration based on artificial bee colony algorithm for reducing randomness of the global-best harmony search (GHS) algorithm, as well as two perturbation schemes for avoiding premature convergence, are integrated. In addition, two parameters of IGHS, harmony memory consideration rate and pitch adjusting rate, are dynamically updated based on a composite function composed of a linear time-varying function, a periodic function and a sign function in view of approximate periodicity of evolution in nature. Experimental results tested on twenty-eight benchmark functions indicate that IGHS is far better than basic harmony search (HS) algorithm and GHS. In further study, IGHS has also been compared with other eight well known metaheuristics. The results show that IGHS is better than or at least similar to those approaches on most of test functions.